\documentclass{sig-alternate-05-2015}
\usepackage[utf8]{inputenc}
\newtheorem{theorem}{Theorem}%[section]

\def\inputfig#1{\input #1}
\def\inputtex#1{\input #1}
\def\inputal#1{\input #1}
\def\inputcode#1{\input #1}

\def\mitloop{MIT \texttt{loop}}

\inputtex{logos.tex}
\inputtex{refmacros.tex}
\inputtex{other-macros.tex}

\begin{document}

\conferenceinfo{10th ELS}{April 3--4, 2017, Brussels, Belgium}
\setcopyright{rightsretained}
\title{Removing redundant tests by replicating control paths
\titlenote{
This work was supported by the French National Research Agency (ANR project GraphEn / ANR-15-CE40-0009).
}}

\numberofauthors{1}
\author{\alignauthor
Irène Durand\\
Robert Strandh\\
\affaddr{University of Bordeaux}\\
\affaddr{351, Cours de la Libération}\\
\affaddr{Talence, France}\\
\email{irene.durand@u-bordeaux.fr}
\email{robert.strandh@u-bordeaux.fr}}

\maketitle

\begin{abstract}
We describe a technique for removing redundant tests in intermediate
code by replicating the control paths between two identical tests, the
second of which is dominated by the first.  The two replicas encode
different outcomes of the test, making it possible to remove the
second of the two.  Our technique uses local graph rewriting, making
its correctness easy to prove.  We also present a proof that the
rewriting always terminates.  This technique can be used to eliminate
multiple tests that occur naturally such as the test for
\texttt{cons}-ness when both \texttt{car} and \texttt{cdr} are applied
to the same object, but we also show how this technique can be used to
automatically create specialized versions of general code, for example
in order to create fast specialized versions of sequence functions
such as \texttt{find} depending on the type of the sequence and the
values of the keyword arguments supplied.
\end{abstract}

\begin{CCSXML}
<ccs2012>
<concept>
<concept_id>10003752.10003766.10003767.10003769</concept_id>
<concept_desc>Theory of computation~Rewrite systems</concept_desc>
<concept_significance>500</concept_significance>
</concept>
<concept>
<concept_id>10011007.10011006.10011041</concept_id>
<concept_desc>Software and its engineering~Compilers</concept_desc>
<concept_significance>500</concept_significance>
</concept>
</ccs2012>
\end{CCSXML}

\ccsdesc[500]{Theory of computation~Rewrite systems}
\ccsdesc[500]{Software and its engineering~Compilers}

\printccsdesc

\keywords{Intermediate code, compiler optimization, local graph rewriting}

\inputtex{sec-introduction.tex}
\inputtex{sec-previous.tex}
\inputtex{sec-our-method.tex}
\inputtex{sec-benefits.tex}
\inputtex{sec-conclusions.tex}
\inputtex{sec-acknowledgments.tex}

\bibliographystyle{abbrv}
\bibliography{path-replication}
\end{document}
